public class CircularSuffixArray {
    // circular suffix array of s
    // 先构建原始循环后缀数组，再用基数排序得到排序后的循环后缀数组，然后就easy了
    private String s;
    private int index[];

    public CircularSuffixArray(String s) {
        this.s = s;
        s += s;
        int[] circleSuffixArray = new int[length()];
        index = new int[length()];
        // 得到原始后缀循环数组和index数组
        for (int i = 0; i < length(); i++) {
            index[i] = i;
            circleSuffixArray[i] = i;
        }
        sort(s,circleSuffixArray, length(), index);
    }

    private static void sort(String s,int[] a, int W, int[] index) {
        int R = 256;
        int N = a.length;
        int[] aux = new int[N];
        int[] copIndex = new int[N];
        for (int d = W - 1; d >= 0; d--) {
            int[] count = new int[R + 1];
            for (int i = 0; i < N; i++)
                count[s.charAt(d+a[i]) + 1]++;
            for (int r = 0; r < R; r++)
                count[r + 1] += count[r];
            for (int i = 0; i < N; i++) {
                int tmp = count[s.charAt(d+a[i])]++;
                aux[tmp] = a[i];
                copIndex[tmp] = index[i];
            }
            for (int i = 0; i < N; i++) {
                a[i] = aux[i];
                index[i] = copIndex[i];
            }
        }
    }

    // length of s
    public int length() {
        return s.length();
    }

    // returns index of ith sorted suffix
    public int index(int i) {
        return index[i];
    }

    // unit testing (required)
    public static void main(String[] args) {
        CircularSuffixArray a = new CircularSuffixArray("ABRACADABRA!");
        System.out.println(a.index(0));
    }
}
